package algorithms.graph;

import algorithms.graph.Graph;

import java.util.LinkedList;
import java.util.Stack;

public class BreadthFirstPaths {

	private boolean[] marked;
	private int[] edgeTo;		//从起点到一个顶点的已知路径上的最后一个顶点
	private final int s;		//起点
	
	public BreadthFirstPaths(Graph g, int s) {
		this.s = s;
		marked = new boolean[g.V()];
		edgeTo = new int[g.V()];
		bfs(g, s);
	}
	
	private void bfs(Graph g, int s){
		LinkedList<Integer> queue = new LinkedList<Integer>();
		marked[s] = true;
		queue.push(s);
		while(!queue.isEmpty()){
			int v = queue.poll();
			for(int w : g.adj(v)){
				if(!marked[w]){
					edgeTo[w] = v;
					marked[w] = true;
					queue.push(w);
				}
			}
		}
	}
	
	public boolean hasPathTo(int v){
		return marked[v];
	}
	
	// s -> v 的路径
	public Iterable<Integer> pathTo(int v) {
		if (!hasPathTo(v))
			return null;
		Stack<Integer> path = new Stack<Integer>();
		for (int x = v; x != s; x = edgeTo[x])
			path.push(x);
		path.push(s);
		return path;
	}
	
}
